\subsection{Centralized intervention strategies}
\label{sec:optimization}
In this section, we study centralized intervention strategies. The
goal is to minimize the social cost define in Section
\ref{sec:intervention-framework}. Here we restrict our graphs to be
static, and assume there is no behavior change. Therefore, the problem
boils down to find a strategy vector $\vec{a}$ such that
\[\sum_v\cost_v\left(\bar{a},d\right) = \sum_v \sqb{C_v a_v +(1-a_v)L_v\cdot p_v\left(\bar{a},d\right)}\]
is minimized.

\subsubsection{Our results}
In \cite{kumar+rss:icdcs}, we have designed an algorithm that is an
$O(\log n)$-approximation for the $d=\infty$ case (recall $d$ is
locality parameter), and a $2d$-approximation for $d<\infty$.  A
logarithmic-approximation for the $d=\infty$ case was also obtained
independently by~\cite{chen+dk:vaccinate}.

\subsubsection{Proposed research}
If time permits, I'd like to try the following problem.
\begin{itemize}
\item Consider the same problem in the setting where arbitrary disease
  transmission probability and behavior change are allowed. One hurdle
  for such problem is, with arbitrary disease transmission
  probability, even calculating the cost of an individual is hard. We
  plan to pursue two directions. One is by using the notion of
  cut-based decompositions of networks. Thanks to an elegant result of
  R\"{a}cke that approximates arbitrary networks by
  trees~\cite{racke:decompose} (note that vaccination strategy is
  equivalent to vertex cut in graphs).  The other is by building on
  work of~\cite{chung+hl:giant09} for percolation in arbitrary finite
  graphs.  Their results imply that for constant-degree networks, the
  cost of an intervention strategy is asymptotically dominated by
  those clusters (obtained after applying the intervention) that have
  high second order average degree, defined as $\sum_v d(v)^2/(\sum_v
  d(v))$, where $d(v)$ denotes the degree of node $v$ in the cluster.
  It is still challenging to extend these ideas to derive efficient
  approximation algorithms.
\end{itemize}

